The design, synthesis, and structure-activity relationships (SAR) of a series of novel proline and pyrrolidine based melanocortin receptor (MCR) agonists are described. To validate a conformationally constrained Arg-Nal dipeptide analogue strategy, we first synthesized and evaluated a test set of cis-(2R,4R)-proline analogues (21a-g). All of these compounds showed significant binding and agonist potency at the hMC1R, hMC3R, and hMC4R. Potent cis-(2S,4R)-pyrrolidine based MCR agonists (35a-g) were subsequently developed by means of this design approach. A SAR study directed toward probing the effect of the two chiral centers in the pyrrolidine ring on biological activity revealed the importance of the (S) absolute configuration at the 2-position for binding affinity, agonist potency, and receptor selectivity. Among the four sets of the pyrrolidine diastereomers investigated, analogues with the (2S,4R) configuration were the most potent agonists across the three receptors, followed by those possessing the (2S,4S) configuration.